# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName : shortes_path.py
# @Time     : 2024/1/28 16:18
# @Author   : Robot-Zsj
"""
description:

想知道从节点K到所有节点至少花费多少时间，只要求出节点K到每个节点的时间长度，从中取最大即可，因此可将问题转化成一个求节点K到每个节点所需最短时间。

用一个列表K2other来存储节点K到每个节点的最短时长，通过判断某一节点作为中间节点能否使节点K到另外一个节点Q的时长缩短来更新K2other，

并且由于K到Q最短时长的更新可能导致整体的变化，因此将节点Q放入队列中，将其作为中间节点再更新K2other。


link: 两个节点之间时长的列表
N变量：表示节点总数
K变量：表示起点
graph变量：各个节点之间的邻接矩阵，graph[i][j]代表节点i到节点j所需时间长度
K2other变量：表示节点K到各个节点的时间长度
queue变量：表示队列
current变量：表示取出的队头节点。
"""

from collections import deque


def shortest_path(link, N, K):
    # 首先根据link对graph进行初始化，如果两个节点之间没有直达路劲，则设置为正无穷，对于graph[i][i]，即节点与自身的时长为0.
    graph = [[float('inf') for _ in range(N)] for _ in range(N)]
    for d in link:
        x = d[0] - 1
        y = d[1] - 1
        graph[x][y] = d[2]
    for i in range(N):
        graph[i][i] = 0
    # 初始化K2other变量，由于入队的第一个节点是K节点，因此可以只更新K节点到自身的距离为0，其余节点在进入迭代之后再做更新，同时将K节点入队。
    K2other = [float('inf') for _ in range(N)]
    K2other[K - 1] = 0
    queue = deque([K - 1])

    # 进入迭代之后，取出队头节点current，然后遍历所有节点，判断以current为中间节点是否能使节点K到各个节点之间的时间长度缩短，
    # 即对比K2other[current]+graph[current][i]与K2other[i]的大小，若前者小于后者，则说明以current为中间节点能够使K2other进一步优化。
    while queue:
        current = queue.popleft()
        for i in range(N):
            if K2other[current] + graph[current][i] < K2other[i]:
                K2other[i] = K2other[current] + graph[current][i]
                queue.append(i)
    if float('inf') in K2other:
        return -1
    return max(K2other)


_link = [[2, 3, 1], [2, 4, 1], [3, 1, 1]]
_N = 4
_K = 2
print(shortest_path(_link, _N, _K))
